We study the extent of independence needed to approximate the product ofbounded random variables in expectation, a natural question that hasapplications in pseudorandomness and min-wise independent hashing. For random variables whose absolute value is bounded by $1$, we give an errorbound of the form $\sigma^{\Omega(k)}$ where $k$ is the amount of independenceand $\sigma^2$ is the total variance of the sum. Previously known bounds onlyapplied in more restricted settings, and were quanitively weaker. We use thisto give a simpler and more modular analysis of a construction of min-wiseindependent hash functions and pseudorandom generators for combinatorialrectangles due to Gopalan et al., which also slightly improves theirseed-length. Our proof relies on a new analytic inequality for the elementary symmetricpolynomials $S_k(x)$ for $x \in \mathbb{R}^n$ which we believe to be ofindependent interest. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are smallrelative to $|S_{k-1}(x)|$ for some $k>0$ then $|S_\ell(x)|$ is also small forall $\ell > k$. From these, we derive tail bounds for the elementary symmetricpolynomials when the inputs are only $k$-wise independent.
展开▼
